home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C++ / Libraries / KPlib 1.2.1 / KPArray.h next >
Encoding:
Text File  |  1994-11-07  |  15.9 KB  |  615 lines  |  [TEXT/R*ch]
  1. // A module of KPLib v1.2.1.
  2. // Written by Keith Pomakis during the summer of 1994.
  3. // Released to the public domain on October 10, 1994.
  4.  
  5. #ifndef KP_ARRAY_DEFINED
  6. #define KP_ARRAY_DEFINED
  7.  
  8. #include <iostream.h>
  9. #include <stdlib.h>
  10. #include "KPbasic.h"
  11.  
  12. // Assumes Element has a default constructor and operator=().
  13.  
  14. template <class Element>
  15. class KPArray {
  16.     public:
  17.         KPArray();
  18.         KPArray(int size);
  19.         KPArray(int size, const Element &init_element);
  20.         KPArray(const KPArray &array);
  21.         virtual ~KPArray();
  22.         KPArray &operator=(const KPArray &array);
  23.         Element &operator[](int index);
  24.         const Element &operator[](int index) const;
  25.         int size() const;
  26.         bool is_empty() const;
  27.         void resize(int new_size);
  28.         void resize(int new_size, const Element &init_element);
  29.         void set_all_to(const Element &element);
  30.     protected:
  31.         virtual void error(const char *msg) const;
  32.         int my_size;
  33.         Element *my_elements;
  34. };
  35.  
  36. // Assumes Element has the above plus operator==().
  37.  
  38. template <class Element>
  39. class KPComparableArray: public KPArray<Element> {
  40.     public:
  41.         KPComparableArray();
  42.         KPComparableArray(int size);
  43.         KPComparableArray(int size, const Element &init_element);
  44.         KPComparableArray(const KPComparableArray &array);
  45.         KPComparableArray(const KPArray<Element> &array);
  46.         virtual ~KPComparableArray();
  47.         KPComparableArray &operator=(const KPArray<Element> &array);
  48.         bool operator==(const KPComparableArray &array) const;
  49.         bool operator!=(const KPComparableArray &array) const;
  50.         bool contains(const Element &element) const;
  51.         int occurrences_of(const Element &element) const;
  52.         int index_of(const Element &element) const;
  53.     protected:
  54.         virtual void error(const char *msg) const;
  55. };
  56.  
  57. // Assumes Element has the above plus operator<().  Note that this operator
  58. // must place a total ordering on the set of Elements.
  59.  
  60. template <class Element>
  61. class KPSortableArray: public KPComparableArray<Element> {
  62.     public:
  63.         KPSortableArray();
  64.         KPSortableArray(int size);
  65.         KPSortableArray(int size, const Element &init_element);
  66.         KPSortableArray(const KPSortableArray &array);
  67.         KPSortableArray(const KPArray<Element> &array);
  68.         virtual ~KPSortableArray();
  69.         KPSortableArray &operator=(const KPArray<Element> &array);
  70.         void sort();
  71.         Element &min();
  72.         const Element &min() const;
  73.         Element &max();
  74.         const Element &max() const;
  75.     protected:
  76.         virtual void error(const char *msg) const;
  77.         int findpivot(int i, int j);
  78.         int partition(int l, int r, const Element &pivot);
  79.         void quicksort(int i, int j);
  80. };
  81.  
  82. /****************************************************************************/
  83.  
  84. template <class Element>
  85. inline
  86. KPArray<Element>::KPArray(): my_size(0)
  87. {
  88.     /* do nothing */
  89. }
  90.  
  91. /****************************************************************************/
  92.  
  93. template <class Element>
  94. KPArray<Element>::KPArray(int size)
  95. {
  96.     if (size < 0)
  97.         error("KPArray() - size of KPArray must be non-negative");
  98.  
  99.     my_size = size;
  100.     my_elements = new Element[size];
  101.     check_mem(my_elements);
  102. }
  103.  
  104. /****************************************************************************/
  105.  
  106. template <class Element>
  107. KPArray<Element>::KPArray(int size, const Element &init_element)
  108. {
  109.     if (size < 0)
  110.         error("KPArray() - size of KPArray must be non-negative");
  111.  
  112.     my_size = size;
  113.     if (my_size > 0) {
  114.         my_elements = new Element[size];
  115.         check_mem(my_elements);
  116.         for (int i=0; i<size; i++)
  117.             my_elements[i] = init_element;
  118.     }
  119. }
  120.  
  121. /****************************************************************************/
  122.  
  123. template <class Element>
  124. KPArray<Element>::KPArray(const KPArray<Element> &array)
  125. {
  126.     my_size = array.my_size;
  127.     if (my_size > 0) {
  128.         my_elements = new Element[my_size];
  129.         check_mem(my_elements);
  130.         for (int i=0; i<my_size; i++)
  131.             my_elements[i] = array.my_elements[i];
  132.     }
  133. }
  134.  
  135. /****************************************************************************/
  136.  
  137. template <class Element>
  138. inline
  139. KPArray<Element>::~KPArray()
  140. {
  141.     if (my_size > 0)
  142.         delete [] my_elements;
  143. }
  144.  
  145. /****************************************************************************/
  146.  
  147. template <class Element>
  148. KPArray<Element> &
  149. KPArray<Element>::operator=(const KPArray<Element> &array)
  150. {
  151.     if (this == &array)
  152.         return *this;
  153.  
  154.     if (my_size > 0)
  155.         delete [] my_elements;
  156.  
  157.     my_size = array.my_size;
  158.     if (my_size > 0) {
  159.         my_elements = new Element[my_size];
  160.         check_mem(my_elements);
  161.         for (int i=0; i<my_size; i++)
  162.             my_elements[i] = array.my_elements[i];
  163.     }
  164.     return *this;
  165. }
  166.  
  167. /****************************************************************************/
  168.  
  169. template <class Element>
  170. inline Element &
  171. KPArray<Element>::operator[](int index)
  172. {
  173.     if (index < 0 || index >= my_size)
  174.         error("operator[] - invalid index");
  175.  
  176.     return my_elements[index];
  177. }
  178.  
  179. /****************************************************************************/
  180.  
  181. template <class Element>
  182. inline const Element &
  183. KPArray<Element>::operator[](int index) const
  184. {
  185.     if (index < 0 || index >= my_size)
  186.         error("operator[] - invalid index");
  187.  
  188.     return my_elements[index];
  189. }
  190.  
  191. /****************************************************************************/
  192.  
  193. template <class Element>
  194. inline int
  195. KPArray<Element>::size() const
  196. {
  197.     return my_size;
  198. }
  199.  
  200. /****************************************************************************/
  201.  
  202. template <class Element>
  203. inline bool
  204. KPArray<Element>::is_empty() const
  205. {
  206.     return (my_size == 0);
  207. }
  208.  
  209. /****************************************************************************/
  210.  
  211. template <class Element>
  212. void
  213. KPArray<Element>::resize(int new_size)
  214. {
  215.     if (my_size == new_size)
  216.         return;
  217.  
  218.     if (new_size < 0)
  219.         error("resize() - size of KPArray must be non-negative");
  220.  
  221.     if (new_size > 0) {
  222.         Element *new_space = new Element[new_size];
  223.         check_mem(new_space);
  224.  
  225.         const int savable_elements = ::min(my_size, new_size);
  226.         for (int i=0; i<savable_elements; i++)
  227.             new_space[i] = my_elements[i];
  228.  
  229.         if (my_size > 0)
  230.             delete [] my_elements;
  231.         my_elements = new_space;
  232.     }
  233.     else
  234.         delete [] my_elements;
  235.  
  236.     my_size = new_size;
  237. }
  238.  
  239. /****************************************************************************/
  240.  
  241. template <class Element>
  242. void
  243. KPArray<Element>::resize(int new_size, const Element &init_element)
  244. {
  245.     if (my_size == new_size)
  246.         return;
  247.  
  248.     if (new_size < 0)
  249.         error("resize() - size of KPArray must be non-negative");
  250.  
  251.     if (new_size > 0) {
  252.         Element *new_space = new Element[new_size];
  253.         check_mem(new_space);
  254.  
  255.         int i;
  256.         const int savable_elements = ::min(my_size, new_size);
  257.         for (i=0; i<savable_elements; i++)
  258.             new_space[i] = my_elements[i];
  259.  
  260.         if (my_size > 0)
  261.             delete [] my_elements;
  262.         my_elements = new_space;
  263.  
  264.         for (i=my_size; i<new_size; i++)
  265.             my_elements[i] = init_element;
  266.     }
  267.     else
  268.         delete [] my_elements;
  269.  
  270.     my_size = new_size;
  271. }
  272.  
  273. /****************************************************************************/
  274.  
  275. template <class Element>
  276. void
  277. KPArray<Element>::set_all_to(const Element &element)
  278. {
  279.     for (int i=0; i<my_size; i++)
  280.         my_elements[i] = element;
  281. }
  282.  
  283. /****************************************************************************/
  284.  
  285. template <class Element>
  286. void
  287. KPArray<Element>::error(const char *msg) const
  288. {
  289.     cerr << "KPArray: " << msg << '\n';
  290.     exit(EXIT_FAILURE);
  291. }
  292.  
  293. /****************************************************************************/
  294.  
  295. template <class Element>
  296. inline
  297. KPComparableArray<Element>::KPComparableArray(): KPArray<Element>()
  298. { /* do nothing new. */ }
  299.  
  300. /****************************************************************************/
  301.  
  302. template <class Element>
  303. inline
  304. KPComparableArray<Element>::KPComparableArray(int size): KPArray<Element>(size)
  305. { /* do nothing new. */ }
  306.  
  307. /****************************************************************************/
  308.  
  309. template <class Element>
  310. inline
  311. KPComparableArray<Element>::KPComparableArray(int size,
  312.             const Element &init_element): KPArray<Element>(size, init_element)
  313. { /* do nothing new. */ }
  314.  
  315. /****************************************************************************/
  316.  
  317. template <class Element>
  318. inline
  319. KPComparableArray<Element>::KPComparableArray(
  320.             const KPComparableArray<Element> &array): KPArray<Element>(array)
  321. { /* do nothing new. */ }
  322.  
  323. /****************************************************************************/
  324.  
  325. template <class Element>
  326. inline
  327. KPComparableArray<Element>::KPComparableArray(const KPArray<Element> &array):
  328.                                                 KPArray<Element>(array)
  329. { /* do nothing new. */ }
  330.  
  331. /****************************************************************************/
  332.  
  333. template <class Element>
  334. inline
  335. KPComparableArray<Element>::~KPComparableArray()
  336. { /* do nothing new. */ }
  337.  
  338. /****************************************************************************/
  339.  
  340. template <class Element>
  341. inline KPComparableArray<Element> &
  342. KPComparableArray<Element>::operator=(const KPArray<Element> &array)
  343. {
  344.     KPArray<Element>::operator=(array);
  345.     return *this;
  346. }
  347.  
  348. /****************************************************************************/
  349.  
  350. template <class Element>
  351. bool
  352. KPComparableArray<Element>::operator==(const KPComparableArray<Element> &array)
  353.                                                                         const
  354. {
  355.     if (this == &array)
  356.         return true;
  357.     
  358.     if (my_size != array.my_size)
  359.         return false;
  360.  
  361.     for (int i=0; i<my_size; i++)
  362.         if (!(my_elements[i] == array.my_elements[i]))
  363.             return false;
  364.     
  365.     return true;
  366. }
  367.  
  368. /****************************************************************************/
  369.  
  370. template <class Element>
  371. inline bool
  372. KPComparableArray<Element>::operator!=(const KPComparableArray<Element> &array)
  373.                                                                         const
  374. {
  375.     return !(*this == array);
  376. }
  377.  
  378. /****************************************************************************/
  379.  
  380. template <class Element>
  381. inline bool
  382. KPComparableArray<Element>::contains(const Element &element) const
  383. {
  384.     return (index_of(element) != -1);
  385. }
  386.  
  387. /****************************************************************************/
  388.  
  389. template <class Element>
  390. int
  391. KPComparableArray<Element>::occurrences_of(const Element &element) const
  392. {
  393.     int occurrences = 0;
  394.  
  395.     for (int i=0; i<my_size; i++)
  396.         if (my_elements[i] == element)
  397.             occurrences++;
  398.  
  399.     return occurrences;
  400. }
  401.  
  402. /****************************************************************************/
  403.  
  404. template <class Element>
  405. int
  406. KPComparableArray<Element>::index_of(const Element &element) const
  407. {
  408.     for (int i=0; i<my_size; i++)
  409.         if (my_elements[i] == element)
  410.             return i;
  411.  
  412.     return -1;
  413. }
  414.  
  415. /****************************************************************************/
  416.  
  417. template <class Element>
  418. void
  419. KPComparableArray<Element>::error(const char *msg) const
  420. {
  421.     cerr << "KPComparableArray: " << msg << '\n';
  422.     exit(EXIT_FAILURE);
  423. }
  424.  
  425. /****************************************************************************/
  426.  
  427. template <class Element>
  428. inline
  429. KPSortableArray<Element>::KPSortableArray(): KPComparableArray<Element>()
  430. { /* do nothing new. */ }
  431.  
  432. /****************************************************************************/
  433.  
  434. template <class Element>
  435. inline
  436. KPSortableArray<Element>::KPSortableArray(int size):
  437.                                             KPComparableArray<Element>(size)
  438. { /* do nothing new. */ }
  439.  
  440. /****************************************************************************/
  441.  
  442. template <class Element>
  443. inline
  444. KPSortableArray<Element>::KPSortableArray(int size,
  445.     const Element &init_element): KPComparableArray<Element>(size, init_element)
  446. { /* do nothing new. */ }
  447.  
  448. /****************************************************************************/
  449.  
  450. template <class Element>
  451. inline
  452. KPSortableArray<Element>::KPSortableArray(const KPSortableArray<Element>
  453.                                     &array): KPComparableArray<Element>(array)
  454. { /* do nothing new. */ }
  455.  
  456. /****************************************************************************/
  457.  
  458. template <class Element>
  459. inline
  460. KPSortableArray<Element>::KPSortableArray(const KPArray<Element> &array):
  461.                                             KPComparableArray<Element>(array)
  462. { /* do nothing new. */ }
  463.  
  464. /****************************************************************************/
  465.  
  466. template <class Element>
  467. inline
  468. KPSortableArray<Element>::~KPSortableArray()
  469. { /* do nothing new. */ }
  470.  
  471. /****************************************************************************/
  472.  
  473. template <class Element>
  474. inline KPSortableArray<Element> &
  475. KPSortableArray<Element>::operator=(const KPArray<Element> &array)
  476. {
  477.     KPComparableArray<Element>::operator=(array);
  478.     return *this;
  479. }
  480.  
  481. /****************************************************************************/
  482.  
  483. template <class Element>
  484. int
  485. KPSortableArray<Element>::findpivot(int i, int j)
  486. {
  487.     const Element &first = my_elements[i];
  488.     for (int k=i+1; k<=j; k++) {
  489.         if (first < my_elements[k])
  490.             return k;
  491.         else if (my_elements[k] < first)
  492.             return i;
  493.     }
  494.     return -1;
  495. }
  496.  
  497. template <class Element>
  498. int
  499. KPSortableArray<Element>::partition(int l, int r, const Element &pivot)
  500. {
  501.     do {
  502.         swap(my_elements[l], my_elements[r]);
  503.         while (my_elements[l] < pivot)
  504.             l++;
  505.         while (!(my_elements[r] < pivot))
  506.             r--;
  507.     } while (l <= r);
  508.     return l;
  509. }
  510.  
  511. template <class Element>
  512. void
  513. KPSortableArray<Element>::quicksort(int i, int j)
  514. {
  515.     Element pivot;
  516.     int k, index;
  517.  
  518.     index = findpivot(i, j);
  519.     if (index != -1) {
  520.         pivot = my_elements[index];
  521.         k = partition(i, j, pivot);
  522.         quicksort(i, k-1);
  523.         quicksort(k, j);
  524.     }
  525. }
  526.  
  527. template <class Element>
  528. inline void
  529. KPSortableArray<Element>::sort()
  530. {
  531.     quicksort(0, my_size-1);
  532. }
  533.  
  534. /****************************************************************************/
  535.  
  536. template <class Element>
  537. Element &
  538. KPSortableArray<Element>::min()
  539. {
  540.     if (my_size < 1)
  541.         error("min() - empty array");
  542.  
  543.     int min_index = 0;
  544.     for (int i=1; i<my_size; i++)
  545.         if (my_elements[i] < my_elements[min_index])
  546.             min_index = i;
  547.  
  548.     return my_elements[min_index];
  549. }
  550.  
  551. /****************************************************************************/
  552.  
  553. template <class Element>
  554. const Element &
  555. KPSortableArray<Element>::min() const
  556. {
  557.     if (my_size < 1)
  558.         error("min() - empty array");
  559.  
  560.     int min_index = 0;
  561.     for (int i=1; i<my_size; i++)
  562.         if (my_elements[i] < my_elements[min_index])
  563.             min_index = i;
  564.  
  565.     return my_elements[min_index];
  566. }
  567.  
  568. /****************************************************************************/
  569.  
  570. template <class Element>
  571. Element &
  572. KPSortableArray<Element>::max()
  573. {
  574.     if (my_size < 1)
  575.         error("max() - empty array");
  576.  
  577.     int max_index = 0;
  578.     for (int i=1; i<my_size; i++)
  579.         if (my_elements[max_index] < my_elements[i])
  580.             max_index = i;
  581.  
  582.     return my_elements[max_index];
  583. }
  584.  
  585. /****************************************************************************/
  586.  
  587. template <class Element>
  588. const Element &
  589. KPSortableArray<Element>::max() const
  590. {
  591.     if (my_size < 1)
  592.         error("max() - empty array");
  593.  
  594.     int max_index = 0;
  595.     for (int i=1; i<my_size; i++)
  596.         if (my_elements[max_index] < my_elements[i])
  597.             max_index = i;
  598.  
  599.     return my_elements[max_index];
  600. }
  601.  
  602. /****************************************************************************/
  603.  
  604. template <class Element>
  605. void
  606. KPSortableArray<Element>::error(const char *msg) const
  607. {
  608.     cerr << "KPSortableArray: " << msg << '\n';
  609.     exit(EXIT_FAILURE);
  610. }
  611.  
  612. /****************************************************************************/
  613.  
  614. #endif /* KP_ARRAY_DEFINED */
  615.